package leetcode.other.p33;

class Solution {
    public int findMin(int[] nums) {
        int l = 0;
        int r = nums.length - 1;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] > nums[r]) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        return l;
    }

    public int find(int[] nums, int fromIndex, int endIndex, int target) {
        int l = fromIndex;
        int r = endIndex;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] < target) {
                l = mid + 1;
            } else if(nums[mid] > target) {
                r = mid - 1;
            } else {
                return mid;
            }
        }
        return -1;
    }

    public int search(int[] nums, int target) {
        // 先通过二分找到最小值，同p153
        int minIdx = findMin(nums);
        int res = 0;
        if (target > nums[nums.length - 1]) {
            res = find(nums, 0, minIdx - 1, target);
        } else {
            res = find(nums, minIdx, nums.length - 1, target);
        }
        return res;
    }

    public static void main(String[] args) {
        //示例 1：
        //输入：nums = [4,5,6,7,0,1,2], target = 0
        //输出：4
        System.out.println(new Solution().search(new int[]{4, 5, 6, 7, 0, 1, 2}, 0));
        //示例 2：
        //输入：nums = [4,5,6,7,0,1,2], target = 3
        //输出：-1
        System.out.println(new Solution().search(new int[]{4, 5, 6, 7, 0, 1, 2}, 3));
        //示例 3：
        //输入：nums = [1], target = 0
        //输出：-1
        System.out.println(new Solution().search(new int[]{1}, 0));
        //示例 4：
        //输入：nums = [1,3,5], target = 3
        //输出：1
        System.out.println(new Solution().search(new int[]{1, 3, 5}, 3));
    }
}